package leetcode.L1000;

import java.util.HashMap;
import java.util.Map;

public class Ex981 {
    /** Initialize your data structure here. */
    Map<String,node> map;

    static class node{
        int timestamp;
        String value;
        node next;
        public node() {

        }
        public node(int timestamp,String value) {
            this.timestamp = timestamp;
            this.value = value;
            this.next = null;
        }
        public node(int timestamp,String value,node n) {
            this.timestamp = timestamp;
            this.value = value;
            this.next = n;
        }
    }

    public Ex981() {
        map = new HashMap<>();

    }

    public void set(String key, String value, int timestamp) {
        if(map.containsKey(key)){
            node first = map.get(key);
            while(first.next!=null&&first.next.timestamp<timestamp){
                first = first.next;
            }
            if(first.timestamp==timestamp){
                first.value = value;
            }else{
                node newNode = new node(timestamp,value,first.next);
                first.next = newNode;
            }

        }else{
            //第一个结点为哨兵结点
            node first = new node();
            first.value = "";
            first.next = new node(timestamp,value);
            map.put(key,first);
        }

    }

    public String get(String key, int timestamp) {
        if(map.containsKey(key)){
            node first = map.get(key);
            while(first.next!=null&&first.next.timestamp<=timestamp){
                first = first.next;
            }
            return first.value;
        }
        return "";
    }

    public static void main(String[] args) {
        Ex981 ex981 = new Ex981();
        ex981.set("foo","bar",1);
        ex981.get("foo",1);
        ex981.get("foo",3);
        ex981.set("foo","bar2",4);
        ex981.get("foo",4);
        ex981.get("foo",5);

    }
}
